package 剑指offer;

/**
 * @description:
 * @author: ywk
 * @date: 2021-03-13
 */
public class 解数独 {

    public static boolean backtrack(char[][] board, int i, int j) {
        int m = 9, n = 9;
        if (j == n) {
            return backtrack(board, i + 1, 0);
        }
        if (i == m) {
            return true;
        }
        if (board[i][j] != '.') {
            return backtrack(board, i, j + 1);
        }
        for (char ch = '1'; ch <= '9'; ch++) {
            if (!isValid(board, i, j, ch)) {
                continue;
            }
            board[i][j] = ch;
            if (backtrack(board, i, j + 1)) {
                return true;
            }
            board[i][j] = '.';
        }
        return false;
    }

    // 判断 board[i][j] 是否可以填⼊ n
    static boolean isValid(char[][] board, int r, int c, char n) {
        for (int i = 0; i < 9; i++) {
            // 判断⾏是否存在重复
            if (board[r][i] == n)
                return false;
            // 判断列是否存在重复
            if (board[i][c] == n)
                return false;
            // 判断 3 x 3 ⽅框是否存在重复
            if (board[(r / 3) * 3 + i / 3][(c / 3) * 3 + i % 3] == n) return false;
        }
        return true;
    }

    public static void print(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                System.out.print(board[i][j] + "\t");
            }
            System.out.println();
        }
    }

    public static char[][] initBoard(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] = '.';
            }
        }
        return board;
    }

    public static void main(String[] args) {
        char[][] chars = initBoard(new char[9][9]);
        backtrack(chars, 0, 0);
        print(chars);
    }
}